import netscape.security.UserTarget;

import javax.print.DocFlavor;
import javax.sql.DataSource;
import java.util.*;
class MaxQueue {
    Queue<Integer> queue;
    Deque<Integer> deque;
    public MaxQueue() {
        queue=new ArrayDeque<>();
        deque=new ArrayDeque<>();
    }

    public int max_value() {
        return deque.isEmpty()?-1:deque.peekFirst();
    }

    public void push_back(int value) {
        while (!deque.isEmpty()&&deque.peekLast()<value){
            deque.pollLast();
        }
        deque.offerLast(value);
        queue.offer(value);
    }

    public int pop_front() {
        if(queue.isEmpty()){
            return -1;
        }
        int tmp=queue.poll();
        if(tmp==deque.peekFirst()){
            deque.pollFirst();
        }
        return tmp;
    }
}

class Solution {
    Map<Integer,Integer> map;
    int row=0;
    int col=0;
    int size=0;
    Random random;
    public Solution(int m, int n) {
        this.row=m;
        this.col=n;
        map=new HashMap<>();
        random=new Random();
        reset();
    }

    public int[] flip() {
        int x=random.nextInt(size);
        size--;
        int y=map.getOrDefault(x,x);
        map.put(x,map.getOrDefault(size,size));
        return new int[]{y/col,y%col};
    }

    public void reset() {
        this.size=row*col;
        map.clear();
    }
}
public class project {
    public int findNthDigit(int n) {
        int digit=1;
        long start=1;
        long count=9;
        while (n>count){
            n-=count;
            digit+=1;
            start*=10;
            count=digit*start*9;
        }
        long num=start+(n-1)/digit;
        return Long.toString(num).charAt((n-1)%digit)-'0';
    }









    public int findNthDigit1(int n) {
        int digit=1;
        long start=1;
        long count=9;
        while (n>count){
            n-=count;
            digit+=1;
            start*=10;
            count=digit*start*9;
        }
        long num=start+(n-1)/digit;
        return Long.toString(num).charAt((n-1)%digit)-'0';
    }



    public int[] nextGreaterElements(int[] nums) {
        int len=nums.length;
        int[] ret=new int[len];
        Arrays.fill(ret,-1);
        Stack<Integer> stack=new Stack<>();
        for(int i=0;i<len*2-1;i++){
            while (!stack.isEmpty()&&nums[stack.peek()]<nums[i%len]){
                ret[stack.pop()]=nums[i%len];
            }
            stack.push(i%len);
        }
        return ret;
    }








    public int[] nextGreaterElements1(int[] nums) {
        int len=nums.length;
        int[] ret=new int[len];
        Arrays.fill(ret,-1);
        Stack<Integer> stack=new Stack<>();
        for(int i=0;i<len*2-1;i++){
            while (!stack.isEmpty()&&nums[stack.peek()]<nums[i%len]){
                ret[stack.pop()]=nums[i%len];
            }
            stack.push(i%len);
        }
        return ret;
    }
}
